﻿#define _CRT_SECURE_NO_WARNINGS 1
//现在有一个长度为 n 的正整数序列，其中只有一种数值出现了奇数次，其他数值均出现偶数次，请你找出那个出现奇数次的数值。
//
//数据范围：
//1≤n≤2×10'6
//输入：
//第一行：一个整数n，表示序列的长度。第二行：n个正整数ai，两个数中间以空格隔开。
//输出：
//一个数，即在序列中唯一出现奇数次的数值。

//有变长数组
#include <stdio.h>

int find(int arr[], int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        result ^= arr[i];
    }
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    int oddOccurrence = find(arr, n);
    printf("%d\n", oddOccurrence);
    return 0;
}

//无变长数组

#include <stdio.h>

int find(int arr[], int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        result ^= arr[i];
    }
    return result;
}

int main() {
    int n;

    scanf("%d", &n);
    int* arr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    int oddOccurrence = find(arr, n);
    printf("%d\n", oddOccurrence);
    free(arr); //不能忘
    return 0;
}


//给定一个长度为n的数组nums，请找到峰值并返回其索引。可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
//1.峰值元素是指其值严格大于左右相邻值的元素。严格大于,不能等于
//2.假设 nums[-1] = nums[n] =−∞
//3.对于所有有效的 i 都有 nums[i] != nums[i + 1]


int find(int* nums, int numsLen) {
    int left = 0, right = numsLen - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        }
        else {
            left = mid + 1;
        }
    }
    return left;
}

